package Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: homechen
 * Date: 2024-03-11
 * Time: 22:57
 */
public class ShellSort {
    public static void shellSort(int[] array, int n) {
        // 先分成 gap 组，分别进行插入  最后是一个接近有序的数组
        int grap = n;
        while (grap > 1) {  // 当 grap 为 1时就是一趟插入排序
            grap = grap / 3 + 1; // grap 的每次取值都会变小
            for (int j = 0; j < grap; j++) {
                for (int i = j; i < n - grap; i += grap) {
                    int end = i;
                    int tmp = array[end + grap]; // 保存这个组的下一个位置
                    while (end >= 0) {  // end 为 0 也要继续
                        if (tmp < array[end]) {
                            array[end + grap] = array[end];
                            end -= grap;
                        } else {
                            break;
                        }
                    }
                    array[end + grap] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 2, 5, 6, 2, 35, 3, 3, 55, 1, 3, 14, 53};
        int n = array.length;
        shellSort(array, n);
        System.out.println(Arrays.toString(array));
    }
}
